#include<iostream>//戴牛的出的邀请赛题
#define maxn  240010
int n,m;

char ch[maxn];
/**************manche 模板*************************/
/* 样例 len返回一这个位置为对称轴的最长回文字符串
  cs下标 0 1 2   0 1 3 4
  	cs	a b a   a a a a
 len下标 01234   0123456
	len 10301   1234321
*/
int len[maxn];
void manche(char*cs)
{
	int n =strlen(cs);
	for (int i = 0, j = 0, k; i < n * 2; i += k, j = max(j - k, 0))
	{
		while (i - j >= 0 && i + j + 1 < n * 2
		&& cs[(i - j) / 2] == cs[(i + j + 1) / 2]) j++;
		len[i] = j;
		for (k = 1; i - k >= 0 && j - k >= 0 && len[i - k] != j - k; k++)
		{
			len[i + k] = min(len[i - k], j - k);
		}
	}
	/*
	for(int i=0; i<2*n;i ++)
	{
		printf("%d ",len[i]);
	}*/	
}
/***************************************/
int f1[maxn][20],f2[maxn][20];

void RMQint()
{
	int i,j,k;
	for(i=0,j=0; i<n; i++,j+=2)
		f1[i][0]=len[j];
	for(i=1,j=1; i<n; i++,j+=2)
		f2[i][0]=len[j];
	for(j=1;(1<<j)<=n; j++)
	{
		k=1<<(j-1);
		for(i=0; i+k<n; i++)
		{
			f1[i][j]=max(f1[i+k][j-1],f1[i][j-1]);
		
			f2[i][j]=max(f2[i+k][j-1],f2[i][j-1]);
		}
	}
}

int rmq1(int l,int r)
{
	if(l>r)	return 0;
	int x,k,dis=r-l+1;
	for(k=0; (1<<k)<=dis; k++);
	k--;
	return max(f1[l][k], f1[r-(1<<k)+1][k]);
}

int rmq2(int l,int r)
{
	if(l>r)	return 0;
	int x,k,dis=r-l+1;
	for(k=0; (1<<k)<=dis; k++);
	k--;
	return max(f2[l][k], f2[r-(1<<k)+1][k]);
}

bool ok(int q,int x,int y)
{
	int half=q/2,l,r;
	int i,j,k;
	if(q%2)
	{
		l=x+half;
		r=y-half;
		if(q<=rmq1(l,r))
			return 1;
	}
	else
	{
		l=x+half;
		r=y-half+1;
		if(q<=rmq2(l,r))
			return 1;
	}
	return 0;
}
int main()
{
#ifndef ONLINE_JUDGE
	freopen("in","r",stdin);
#endif
    int i,j,k,cas,t;
    scanf("%d",cas);
    while(cas--)
    {
		   scanf("%s",ch);
			n=strlen(ch);
			manche(ch);
			RMQint();
			scanf("%d", &t);
			int x,y;
			while(t--)
			{
				scanf("%d%d", &x,&y);
				if(x>y)	swap(x,y);
				x--;y--;
				int r=y-x+1,l=1,ans=0;
				if(r%2==0)r--;
				while(l<=r)
				{
					int mid=(l+r)/2;
					if(mid%2==0)mid--;
					if(ok(mid,x,y))
					{
						ans=max(ans,mid);
						l=mid+2;
					}
					else
					{
						r=mid-2;
					}
				}
				r=y-x+1,l=0;
				if(r%2==1)	r--;
				while(l<=r)
				{
					int mid=(l+r)/2;
					if(mid%2==1)	mid--;
					if(ok(mid,x,y))
					{
						ans=max(ans,mid);
						l=mid+2;
					}
					else
					{
						r=mid-2;
					}
				}
				cout<<ans<<endl;
			}
	}
}


http://blog.163.com/lfw2565295@126/blog/static/12200516201112882117229/
题意﹕给了一字串，长度为。 设为一长度的前缀。 我们把一个长度为的字串说是-回文，若以下条件成立﹕ 
1) 是一个回文； 
2) 的前缀和后缀皆是-回文。 根据定义，任意字串(包括空字串)皆为0-回文。 

现在设若且仅若是一个-回文。 题目要求。 

未进入解之前，首先需要了解一件事。 

引理1 ﹕对于任何长度为的字串，若是回文，是-回文的话，那么的长度为的后缀也是-回文，并且和相同。 

证明1 ：设为字串的逆字串。 假设的长度为的前后缀分别为和。 设，。 那么。 因为，。 因此有和。 若是-回文，则本来。 因此，即也是-回文。 

因此，我们算的时候可以用动态规划﹕ 

那么，答案是求所有前缀回文，并以上述转移方程算出阵列和即可。 
问题是﹕ 如何有效地求所有前缀回文 ？ 

想了几天，实在没有头绪。 如果直接算最长前缀回文的话就很简单的，只需利用失败函数和字串即可。 可是它却不似包含了所有前缀回文的资讯。 因此，放弃了，找到几个日本人写的blog，发现他们用了一个算法，叫 Manacher Algorithm 。 它的目的是求出最长前缀回文的中点，但计算过程则计算了 所有 以某字元可延伸的最长回文长度。 那么此算法则包括找出所有前缀回文，当然，也可以用来找最长前缀回文。 先介绍此算法。 

Manacher算法 
对于长度为的字串，定义为最大整数使得即以第字元为单位的最长可延伸成回文的 半径 。 Manacher给了以下定理﹕ 

定理2 :对于，则有 

和 
。 

证明2 :先证明1)。 因为第字元半径为，当中第字串的半径是。 若果不超过的话，表示第字元的最长可延伸回文被第字元的包含了，则用类似 定理1可以得出(即)。 否则的话，假设，那么第字元的最长可延伸回文超越了第字元的。 但基于类似 定理1 (我们可以把定义为任意回文)，第字元可以再延伸，则不是最长的，因此有矛盾。 所以(最不突破界限的半径作为其半径)。 
对于2)，则可以基于1)的去思考。但第字元的半径则却可以突破第字元的半径。 考虑以下字串﹕ 

01abbaccabbac 
   | i | 
   xy 

现在设。 可以看到但。 

那么，利用 定理2 计算所有字元的半径会否很高效？ 首先，留意到对于第字元，任何第位经1)去更新数值的时候，已经不用重覆计算。 唯一的情况则是2)发生，而且枚举的时候， 2)只会发生在1)之后 。 因此，当枚举至的时候2)发生了，则跟据 定理2 所示，立即跳至第位计算其半径。 因为定理说明，因此找出可直接从算起。 因此可知的跳跃是随的增加而加快的。 算法被证明是的。 我没有很小心的去证明，但可以联想的是少的话，虽然增长很慢(每次移很少)但半径都很少，因此每次迭代都很快完；相反很大的话，我们很快就可以以一次送代算出大部分并且大幅前跃，感觉也很快会完成。 

至于编写的时候，留意上述是适用于偶数长度半径，但奇数长度半径又怎样算出来呢？这里 的方法是插入dummy点来计算半径，但每个字元会被多算一次。 这方法亦可看作迭代的时候移动 半步 ，而枚举其半径时也以 半步为单位移动 。 

计算了之后可以简单地找出前缀回文的末点，然后应用最被初的转移方程计算答案。 

